package sushu;

public class _02埃氏筛法 {
    //求第十万零二个素数
    //自然数n之内的素数个数n/ln(n)
    public static void main(String[] args) {
        solve(100000);
    }

    public static void solve(int N) {
        //N是第N个素数
        //已知在整数X内大概有X/log(X)个素数
        //现在我们要逆推：要想求第N个素数，我们的整数范围是什么
        //length就是整数范围
        int n = 2;
        while (n / Math.log(n) < N) {
            n++;
        }
        //开辟一个数组，下标是自然数，值是标记
        //基本思路是筛选法，把非素数标记出来
        int[] arr = new int[n];
        int x = 2;
        while (x < n) {
            if (arr[x] != 0) {
                //被标记过了，跳过
                x++;
                continue;
            }
            int k = 2;
            while (x * k < n) {
                arr[x * k] = -1;
                k++;
            }
            x++;
        }
        //筛完之后，这个很长的数组里面非素数下标对应的值都是-1
        int sum = 0;
        for (int i = 2; i < arr.length; i++) {
            if (arr[i] == 0) {
                sum++;
            }
            if (sum == N) {
                System.out.println(i);
                return;
            }
        }
    }
}
